// https://pic.leetcode-cn.com/1647580694-POftJu-put.jpg44
//https://leetcode.cn/problems/lru-cache/solution/bu-yong-yu-yan-nei-jian-de-map-gua-dang-feng-zhuan/

//定义ListNode结构体
// function ListNode(key,val) {
//   this.key=key;
//     this.val = val;
//     this.next = null;
// }
class ListNode {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.next = null
    this.prev = null
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.hash = {}
    this.count = 0
    this.dummyHead = new ListNode()
    this.dummyTail = new ListNode()
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }

  get(key) {
    let node = this.hash[key]
    if (node == null) return -1
    this.moveToHead(node)
    return node.value
  }
  put(key, value) {
    let node = this.hash[key]
    if (node == null) {
      if (this.count === this.capacity) {
        this.removeLRUItem()
      }
      let newNode = new ListNode(key, value)
      this.hash[key] = newNode
      this.addToHead(newNode)
      this.count++
    } else {
      node.value = value
      this.moveToHead(node)
    }
  }
  moveToHead(node) {
    this.removeFromList(node)
    this.addToHead(node)
  }

  removeFromList(node) {
    let temp1 = node.prev
    let temp2 = node.next
    temp1.next = temp2
    temp2.prev = temp1
  }
  addToHead(node) {
    node.prev = this.dummyHead
    node.next = this.dummyHead.next
    this.dummyHead.next.prev = node
    this.dummyHead.next = node
  }
  removeLRUItem() {
    let tail = this.popTail()
    delete this.hash[tail.key]
    this.count--
  }
  popTail() {
    let tail = this.dummyTail.prev
    this.removeFromList(tail)
    return tail
  }
}

let lRUCache = new LRUCache(2);
lRUCache.put(1, 1);
lRUCache.put(2, 2);
console.log(lRUCache.get(1));       // returns 1
lRUCache.put(3, 3);    // evicts key 2
console.log(lRUCache.get(2));       // returns -1 (not found)
lRUCache.put(4, 4);    // evicts key 1
console.log(lRUCache.get(1));       // returns -1 (not found)
console.log(lRUCache.get(3));       // returns 3
console.log(lRUCache.get(4));       // returns 4

// lRUCache.get(1);       // returns 1
// lRUCache.put(3, 3);    // evicts key 2
// lRUCache.get(2);       // returns -1 (not found)
// lRUCache.put(4, 4);    // evicts key 1
// lRUCache.get(1);       // returns -1 (not found)
// lRUCache.get(3);       // returns 3
// lRUCache.get(4);       // returns 4


